<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0060)http://www.avatar.se/molbioinfo2001/dynprog/adv_dynamic.html -->
<HTML><HEAD><TITLE>Advanced Dynamic Programming Tutorial</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 9.00.8112.16450"></HEAD>
<BODY bgColor=white>
<H1>
<CENTER>Advanced Dynamic Programming Tutorial</CENTER></H1>If you haven't looked 
at an example of a simple scoring scheme, please go to the <A 
href="http://www.avatar.se/molbioinfo2001/dynprog/dynamic.html">simple dynamic 
programming example</A> 
<P>The following is an example of global sequence alignment using 
Needleman/Wunsch techniques. For this example, the two sequences to be globally 
aligned are 
<P>G A A T T C A G T T A (sequence #1) <BR>G G A T C G A (sequence #2) 
<P>So M = 11 and N = 7 (the length of sequence #1 and sequence #2, respectively) 

<P>An advanced scoring scheme is assumed where 
<UL>
  <LI>S<SUB>i,j</SUB> = 2 if the residue at position i of sequence #1 is the 
  same as the residue at position j of sequence #2 (match score); otherwise 
  <LI>S<SUB>i,j</SUB> = -1 (mismatch score) 
  <LI>w = -2 (gap penalty) </LI></UL>
<H2>
<CENTER>Initialization Step</CENTER></H2>
<P>The first step in the global alignment dynamic programming approach is to 
create a matrix with M + 1 columns and N + 1 rows where M and N correspond to 
the size of the sequences to be aligned. 
<P>The first row and first column of the matrix can be initially filled with 0. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/initial.gif"></CENTER>
<H2>
<CENTER>Matrix Fill Step</CENTER></H2>
<P>One possible (inefficient) solution of the matrix fill step finds the maximum 
global alignment score by starting in the upper left hand corner in the matrix 
and finding the maximal score M<SUB>i,j</SUB> for each position in the matrix. 
In order to find M<SUB>i,j</SUB> for any i,j it is minimal to know the score for 
the matrix positions to the left, above and diagonal to i, j. In terms of matrix 
positions, it is necessary to know M<SUB>i-1,j</SUB>, M<SUB>i,j-1</SUB> and 
M<SUB>i-1, j-1</SUB>. 
<P>For each position, M<SUB>i,j</SUB> is defined to be the maximum score at 
position i,j; i.e. 
<P><PRE><B>M<SUB>i,j</SUB> = MAXIMUM[
     M<SUB>i-1, j-1</SUB> + S<SUB>i,j</SUB></B> (match/mismatch in the diagonal),
     <B>M<SUB>i,j-1</SUB> + w </B>(gap in sequence #1),
     <B>M<SUB>i-1,j</SUB> + w </B>(gap in sequence #2)<B>]</B>
</PRE>
<P>Note that in the example, M<SUB>i-1,j-1</SUB> will be red, M<SUB>i,j-1</SUB> 
will be green and M<SUB>i-1,j</SUB> will be blue. 
<P>Using this information, the score at position 1,1 in the matrix can be 
calculated. Since the first residue in both sequences is a G, S<SUB>1,1 </SUB>= 
2, and by the assumptions stated earlier, w = -2. Thus, M<SUB>1,1</SUB> = 
MAX[M<SUB>0,0</SUB> + 2, M<SUB>1,0</SUB> - 2, M<SUB>0,1 </SUB>- 2] = MAX[2, -2, 
-2]. 
<P>A value of 2 is then placed in position 1,1 of the scoring matrix. Note that 
there is also an arrow placed back into the cell that resulted in the maximum 
score, M[0,0]. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_1.gif"></CENTER>
<HR>

<P>Moving down the first column to row 2, we can see that there is once again a 
match in both sequences. Thus, S<SUB>1,2</SUB> = 2. So M<SUB>1,2</SUB> = 
MAX[M<SUB>0,1</SUB> + 2, M<SUB>1,1</SUB> - 2, M<SUB>0,2</SUB> -2] = MAX[0 + 2, 2 
- 2, 0 - 2] = MAX[2, 0, -2]. 
<P>A value of 2 is then placed in position 1,2 of the scoring matrix and an 
arrow is placed to point back to M[0,1] which led to the maximum score. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_2.gif"></CENTER>
<HR>

<P>Looking at column 1 row 3, there is not a match in the sequences, so S<SUB> 
1,3</SUB> = -1. M<SUB>1,3</SUB> = MAX[M<SUB>0,2</SUB> - 1, M<SUB>1,2</SUB> - 2, 
M<SUB>0,3</SUB> - 2] = MAX[0 - 1, 2 - 2, 0 - 2] = MAX[-1, 0, -2]. 
<P>A value of 0 is then placed in position 1,3 of the scoring matrix and an 
arrow is placed to point back to M[1,2] which led to the maximum score. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_3.gif"></CENTER>
<HR>

<P>We can continue filling in the cells of the scoring matrix using the same 
reasoning. 
<P>Eventually, we get to column 3 row 2. Since there is not a match in the 
sequences at this positon, S<SUB>3,2</SUB> = -1. M<SUB>3,2</SUB> = MAX[ 
M<SUB>2,1</SUB> - 1, M<SUB>3,1</SUB> - 2, M<SUB>2,2</SUB> - 2] = MAX[0 - 1, -1 - 
2, 1 -2] = MAX[-1, -3, -1]. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_8.gif"></CENTER>
<HR>

<P>Note that in the above case, there are two different ways to get the maximum 
score. In such a case, pointers are placed back to all of the cells that can 
produce the maximum score. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_9.gif"></CENTER>
<HR>

<P>The rest of the score matrix can then be filled in. The completed score 
matrix will be as follows: 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_10.gif"></CENTER>
<HR>

<H2>
<CENTER>Traceback Step</CENTER></H2>After the matrix fill step, the maximum 
global alignment score for the two sequences is 3. The traceback step will 
determine the actual alignment(s) that result in the maximum score. 
<P>The traceback step begins in the M,J position in the matrix, i.e. the 
position where both sequences are globally aligned. 
<HR>

<P>Since we have kept pointers back to all possible predacessors, the traceback 
step is simple. At each cell, we look to see where we move next according to the 
pointers. To begin, the only possible predacessor is the diagonal match. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_11.gif"></CENTER>
<P>This gives us an alignment of <PRE>    A
    | 
    A
</PRE>
<P>Note that the blue letters and gold arrows indicate the path leading to the 
maximum score. 
<HR>

<P>We can continue to follow the path using a single pointer until we get to the 
following situation. 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_12.gif"></CENTER>
<P>The alignment at this point is <PRE>    T C A G T T A
    | |   |     | 
    T C _ G _ _ A
</PRE>
<P>Note that there are now two possible neighbors that could result in the 
current score. In such a case, one of the neighbors is arbitrarily chosen. 
<HR>

<P>Once the traceback is completed, it can be seen that there are only two 
possible paths leading to a maximal global alignment. 
<HR>

<P>One possible path is as follows: 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_13.gif"></CENTER>
<P>This gives an alignment of <PRE>   G A A T T C A G T T A
   |   |   | |   |     | 
   G G A _ T C _ G _ _ A
</PRE>
<HR>

<P>The other possible path is as follows: 
<P>
<CENTER><IMG 
src="NeedlemanWunchzAdvanced%20Dynamic%20Programming%20Tutorial_files/advanced_14.gif"></CENTER>
<P>This gives an alignment of <PRE>   G A A T T C A G T T A
   |   | |   |   |     |
   G G A T _ C _ G _ _ A
</PRE>
<HR>

<P>Remembering that the scoring scheme is +2 for a match, -1 for a mismatch, and 
-2 for a gap, both sequences can be tested to make sure that they result in a 
score of 3. <PRE>   G A A T T C A G T T A
   |   |   | |   |     | 
   G G A _ T C _ G _ _ A
 
   + - + - + + - + - - +
   2 1 2 2 2 2 2 2 2 2 2
</PRE>
<P>2 - 1 + 2 - 2 + 2 + 2 - 2 + 2 - 2 - 2 + 2 = 3 <PRE>   G A A T T C A G T T A
   |   | |   |   |     |
   G G A T _ C _ G _ _ A

   + - + + - + - + - - +
   2 1 2 2 2 2 2 2 2 2 2
</PRE>
<P>2 - 1 + 2 + 2 - 2 + 2 - 2 + 2 - 2 - 2 + 2 = 3 
<P>so both of these alignments do indeed result in the maximal alignment score. 
<HR>
<A href="http://www.cec.wustl.edu/~ecr1/">Eric C. Rouchka</A> <A 
href="mailto:ecr@ibc.wustl.edu"><I>ecr@ibc.wustl.edu</I><BR><I>Feb. 4, 
1997</I><BR><A href="http://www.ibc.wustl.edu/CMB/bio5495/">Compuational 
Molecular Biology Home Page</A><BR></BODY></HTML>
